from collections import defaultdict
from typing import List


class Node:
    __slots__ = "val", "parent", "children"

    def __init__(self, val):
        self.val = val
        self.parent = None
        self.children = set()

    @property
    def attr(self):
        return ", ".join("{}: {}".format(k, getattr(self, k)) for k in self.__slots__)

    def __repr__(self):
        return self.__class__.__name__ + "{" + "{}".format(self.attr) + "}"


class Trie:
    class _Node:
        __slots__ = "value", "weight", "children"

        def __init__(self):
            self.value = None
            self.weight = 0
            self.children = {}

        def __contains__(self, ch):
            return ch in self.children

        def __getitem__(self, ch):
            return self.children[ch]

        def __setitem__(self, ch, value):
            self.children[ch] = value

    def __init__(self):
        self.root = self._Node()

    def add(self, word, weight=1):
        """向字典树中添加词语:True=成功添加;False=已有该词"""
        node = self.root
        for ch in word:
            if ch not in node:
                node[ch] = self._Node()
            node.weight += weight
            node = node[ch]
        if node.value is None:
            node.weight += weight
            node.value = word
            return True
        else:
            return False

    def remove(self, word, weight=1):
        """从字典树中移除词数(并不是真的删除，而是移除权重):True=成功移除;False=没有该词"""
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node.weight -= weight
            node = node[ch]
        node.weight -= weight

    def max_xor(self, string):
        bit = MAX_BITS
        res = 0
        node = self.root
        for ch in string:
            if ch == "0":
                if "1" in node and node["1"].weight > 0:
                    node = node["1"]
                    res += 2 ** (bit - 1)
                else:
                    node = node["0"]
            else:  # ch == "1"
                if "0" in node and node["0"].weight > 0:
                    node = node["0"]
                    res += 2 ** (bit - 1)
                else:
                    node = node["1"]
            bit -= 1
        # print(node.value, string)
        return res


MAX_BITS = 18  # 最大二进制位数：2^18 > 2*10^5


class Solution:
    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
        size = len(parents)

        # 构造树
        root = None
        nodes = [Node(i) for i in range(size)]
        for v, parent in enumerate(parents):
            if parent == -1:
                root = nodes[v]
            else:
                nodes[v].parent = nodes[parent]
                nodes[parent].children.add(nodes[v])

        # 整理查询列表
        queries_mapping = defaultdict(list)
        for node, val in queries:
            code1 = bin(node)[2:].zfill(MAX_BITS)
            code2 = bin(val)[2:].zfill(MAX_BITS)
            queries_mapping[code1].append(code2)

        # 构造字典树
        trie = Trie()

        # 返回值
        res = {}

        # 从上往下构造字典树
        def dfs(node):
            code = bin(node.val)[2:].zfill(MAX_BITS)

            trie.add(code)

            # 处理当前结点的查询
            for ask_val in queries_mapping[code]:
                res[(code, ask_val)] = trie.max_xor(ask_val)  # 当前最大异或值
                # print(node.val, "查询:", ask_val, "->", res[code])

            # 处理当前结点的子结点的查询
            for child in node.children:
                dfs(child)

            trie.remove(code)

        # 深度优先搜索
        dfs(root)

        # print(res)

        # 整理最终结果
        ans = []
        for node, val in queries:
            code1 = bin(node)[2:].zfill(MAX_BITS)
            code2 = bin(val)[2:].zfill(MAX_BITS)
            ans.append(res[(code1, code2)])
        return ans


if __name__ == "__main__":
    print(Solution().maxGeneticDifference(parents=[-1, 0, 1, 1],
                                          queries=[[0, 2], [3, 2], [2, 5]]))  # [2,3,7]
    print(Solution().maxGeneticDifference(parents=[3, 7, -1, 2, 0, 7, 0, 2],
                                          queries=[[4, 6], [1, 15], [0, 5]]))  # [6,14,7]

    # 测试用例5/58
    # [6,0,3,9,4]
    print(Solution().maxGeneticDifference(parents=[-1, 0, 0, 0, 3],
                                          queries=[[4, 6], [0, 0], [0, 3], [1, 8], [4, 0]]))
